package leetcode_2401_2500;

import node.Node;
import node.TreeNode;

import java.util.*;

public class LeeCode_2471 {
    public static void main(String[] args) {
        System.out.println(minimumOperations(new TreeNode(1, new TreeNode(3, new TreeNode(7), new TreeNode(6)),
                new TreeNode(2, new TreeNode(5), new TreeNode(4)))));
        System.out.println(minimumOperations(new TreeNode(1, new TreeNode(2), new TreeNode(3))));
    }
    private static int minimumOperations(TreeNode root) {
        int d = getD(root, 0);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < d; i++) {
            list.add(new ArrayList<>());
        }
        dfs(root, list, 0);
        int ans = 0;
        for (List<Integer> son : list) {
            Set<Integer> used = new HashSet<>();
            List<Integer> copy = new ArrayList<>(son);
            copy.sort(Comparator.comparingInt(o -> o));
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < copy.size(); i++) {
                map.put(copy.get(i), i);
            }
            int count = 0;
            for (Integer num : son) {
                if (used.contains(num)) {
                    continue;
                }
                int next = num;
                while (!used.contains(next)) {
                    used.add(next);
                    next = son.get(map.get(next));
                }
                count++;
            }
            ans += son.size() - count;
        }
        return ans;
    }
    private static int getD(TreeNode node, int d){
        if (node == null)
            return d;
        return Math.max(getD(node.left, d + 1), getD(node.right, d + 1));
    }
    private static void dfs(TreeNode node, List<List<Integer>> list, int d){
        if (node == null)
            return;
        dfs(node.left, list, d + 1);
        list.get(d).add(node.val);
        dfs(node.right, list, d + 1);
    }
}
